// 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
//
// 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
//
// 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
//
//
//
// 示例 1:
//
//
// 输入: [3,2,1,5,6,4], k = 2
// 输出: 5
//
//
// 示例 2:
//
//
// 输入: [3,2,3,1,2,4,5,5,6], k = 4
// 输出: 4
//
//
//
// 提示：
//
//
// 1 <= k <= nums.length <= 10⁵
// -10⁴ <= nums[i] <= 10⁴
//
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 1882 👎 0

package leetcode.editor.cn;

import java.util.Arrays;
import java.util.Collections;

// Java：数组中的第K个最大元素
public class P215KthLargestElementInAnArray {
	public static void main(String[] args) {
		Solution solution = new P215KthLargestElementInAnArray().new Solution();
		int[] arr = {3,2,3,1,2,4,5,5,6};
		int kthLargest = solution.findKthLargest(arr, 4);
		System.out.println(kthLargest);
		// TO TEST
	}

	// leetcode submit region begin(Prohibit modification and deletion)
	class Solution {
		public int findKthLargest(int[] nums, int k) {
			quickSort(nums, 0, nums.length - 1, false);
			return nums[k];
		}

		private void  quickSort(int[] target, int left, int right, boolean isAscending) {
			if (left >= right) {
				return;
			}
			int i,j,x;

			i = left;
			j = right;
			x = target[i];
			while (i < j)
			{
				if(isAscending) {
					while (i < j && target[j] > x) {
						j--; // 从右向左找第一个小于x的数
					}

					if (i < j) {
						target[i++] = target[j];
					}
					while (i < j && target[i] < x) {
						i++; // 从左向右找第一个大于x的数
					}
					if (i < j) {
						target[j--] = target[i];
					}
				}else{
					while (i < j && target[j] < x) {
						j--; // 从右向左找第一个大于x的数
					}

					if (i < j) {
						target[i++] = target[j];
					}
					while (i < j && target[i] > x) {
						i++; // 从左向右找第一个小于x的数
					}
					if (i < j) {
						target[j--] = target[i];
					}
				}
			}
			target[i] = x;
			quickSort(target, left, i-1, isAscending); /* 递归调用 */
			quickSort(target, i+1, right, isAscending); /* 递归调用 */
		}
		// leetcode submit region end(Prohibit modification and deletion)
	}

}
